package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/8/14 0014.
 */

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 */
public class 二叉搜索树的后序遍历 {
    public static void main(String[] args) {

        int[] sequence = {3, 2, 4, 6, 5};
        System.out.println(VerifySquenceOfBST(sequence));
    }

    //二叉搜索树的后序遍历的特点是最后一个数为根节点。在前面的序列中可以分为两份，一份是比根节点大的，一份是比根节点小的。
    //先确定出一个下标，左边的小于根节点，下标右边的数大于根节点。
    //从后面往前寻找第一个比根节点小的数，从而确定此下标。然后遍历下标以左的数，若都比根节点小。则以此节点为根的二叉树序列正常
    //然后遍历子树。
    public static boolean VerifySquenceOfBST(int[] sequence) {

        if (sequence.length == 0) return false;
        return judge(sequence, 0, sequence.length - 1);
    }

    private static boolean judge(int[] sequence, int start, int end) {
        if (end <= start) return true;           //递归时返回true的条件。
        int i = end;
        while (i > 0 && sequence[i - 1] > sequence[end]) i--;//找出下标i。
//        int j = i-1;
//        while (j >= 0) {
//            if (sequence[j] > sequence[end]) return false;
//            j--;
//        }
        for (int j = i - 1; j >= 0; j++) if (sequence[j] > sequence[end]) return false;
        return judge(sequence, start, i - 1) && judge(sequence, i, end - 1);
    }
}
